package effizienz;
import java.awt.Color;
import java.util.Random;
import javax.swing.JComponent;
import java.awt.Graphics;

public class Land extends JComponent{
  private static final double XMAX=500;//maximaler x-Wert einer Stadt
  private static final double YMAX=500;//maximaler y-Wert einer Stadt
  private Random zufall;

  /**Diese Liste von Städten wird bei der Erzeugung eines Landes
   * angelegt und kann danach von außen nicht mehr verändert werden.
   */
  protected Stadt[] grundlage;

  /**Summe der IDs aller Städte zum schnellen Test, ob in einer beliebigen
   * Liste von Städten alle Städte des Landes genau einmal vorhanden sind.
   */
  protected long checksum;//die Summe der Stadt-IDs

  /**Eine beliebige Folge von Städten. Bei der graphischen Darstellung
   * werden die erste und letzte verbunden dargestellt.
   */
  protected Stadt[] aktuell;

  /**Erzeugt ein Land mit der gegebenen Anzahl von Städten. Die Lage
   * der Städte ist pseudozufällig und immer gleich.
   * @param anz die gewünschte Anzahl von Städten.
   */
  public Land(int anz){this(anz,0);}

  /**Erzeugt ein Land mit der gegebenen Anzahl von Städten. Die Lage
   * der Städte ist pseudozufällig und immer gleich. Der Anfangswert
   * für den Zufallszahlengenerator ist anzugeben.
   * @param anz die gewünschte Anzahl von Städten.
   * @param seed der Anfangswert für den Zufallszahlengenerator.
   */
  public Land(int anz, long seed){
    grundlage=new Stadt[anz];
    zufall=new Random(seed);
    checksum=0;
    for(int i=0; i<grundlage.length; ++i){
      Stadt s=new Stadt(zufall.nextDouble()*XMAX, zufall.nextDouble()*YMAX);
      grundlage[i]=s;
      checksum+=s.id;
    }
    aktuell=grundlage.clone();
  }

  /**Gibt die Anzahl der Städte in diesem Land zurück.
   * @return die Anzahl der Städte in diesem Land.
   */
  public int stadtAnzahl(){return grundlage.length;}

  /**Gibt die gewünschte Stadt dieses Landes zurück.
   *
   * @param n die Nummer der Stadt.
   * @return die Stadt mit der gegebenen Nummer.
   */
  public Stadt getStadt(int n){return grundlage[n];}

  /**Legt die Reihenfolge fest, in der die Städte anzusteuern sind. Nach
   * der letzten Stadt wird zurückgekehrt in die erste. Es sollte also
   * jede Stadt genau einmal genannt sein, muss aber nicht.
   * 
   * @param reise die Städte in der gewünschten Reihenfolge.
   */
  public void setRundReise(Stadt[] reise){
    aktuell=reise;
    repaint();
  }

  /**Gibt die aktuell angezeigte Rundreise zurück. Wird diese geändert,
   * so sollte <code>setRundReise</code> aufgerufen werden, damit
   * die Änderungen auch dargestellt werden. Solange <code>setRundReise</code>
   * nicht aufgerufen wurde, ist die aktuelle Rundreise die gleiche Folge von
   * Städten, wie bei der Erzeugung des Landes.
   *
   * @return die aktuelle Folge der Städte.
   */
  public Stadt[] getAktuelleRundReise(){return aktuell.clone();}

  /**Gibt zurück, ob eine Folge von Städten alle Städte dieses Landes genau
   * einmal enthält.
   * @param reise die zu testende Folge von Städten.
   * @return true, wenn jede Stadt dieses Landes genau einmal auftritt.
   */
  public boolean isRundReise(Stadt[] reise){
    if(reise==null || reise.length!=grundlage.length) return false;
    long sum=0;
    for(int i=reise.length-1; i>=0; --i){
      if(reise[i]==null) return false;
      sum+=reise[i].id;
    }
    return sum==checksum;
  }

  /**Berechnet die Strecke einer Reise, die der Reihe nach die
   * gegebenen Städte anfährt und am Ende wieder zur ersten zurückkehrt.
   *
   * @param reise die Städte in der gewünschten Reihenfolge.
   * @return die zurückgelegte Strecke (incl. der Rückfahrt zur ersten Stadt).
   *   Falls nicht alle Städte genau einmal angefahren werden, wird das Ergebnis
   *   mit einem negativen Vorzeichen versehen. Der Betrag steht dann aber immer
   *   noch für die zurückgelegte Strecke.
   */
  public double rundReiseStrecke(Stadt[] reise){
    if(reise==null) return Double.NEGATIVE_INFINITY;
    double vorz=1;
    double len=0;
    long sum=0;
    Stadt s=reise[reise.length-1];
    for(int i=0; i<reise.length; ++i){
      Stadt t=reise[i];
      if(s!=null && t!=null){
        len+=Math.hypot(t.x-s.x, t.y-s.y);
        sum+=t.id;
      } else vorz=-1;
      s=t;
    }
    if(sum!=checksum) vorz=-1;
    return vorz*len;
  }

  /**Berechnet die Strecke der aktuell gesetzten Rundreise. Solange nicht
   * <code>setRundReise</code> aufgerufen wurde, wird die Folge der Städte
   * in der Reihenfolge ihrer Erzeugung betrachtet.
   * @return die Strecke der aktuellen Rundreise.
   */
  public double rundReiseStrecke(){return rundReiseStrecke(aktuell);}

  @Override
  public void paintComponent(Graphics g){
    super.paintComponent(g);
    if(aktuell!=null){
      //Verbindungen zeichnen
      g.setColor(isRundReise(aktuell)?Color.BLUE:Color.RED);
      Stadt s=aktuell[aktuell.length-1];
      for(int i=0; i<aktuell.length; ++i){
        Stadt t=aktuell[i];
        if(s!=null && t!=null) g.drawLine((int)s.x,(int)s.y,(int)t.x,(int)t.y);
        s=t;
      }
    }
    //Städte als Punkte zeichnen
    g.setColor(Color.GREEN);
    for(int i=0; i<grundlage.length; ++i){
      Stadt s=grundlage[i];
      g.fillOval((int)(s.x-3),(int)(s.y-3),6,6);
    }
  }

  public static void main(String[] args){
    int anz=20;
    if(args.length>0) anz=Integer.parseInt(args[0]);
    long   gesamtzeit   =0;
    double gesamtstrecke=0;
    for(int i=0; i<10; ++i){
      Land land=new Land(anz, i);
      long zeit=System.currentTimeMillis();
      TSM.tsm(land);
      zeit=System.currentTimeMillis()-zeit;
      gesamtzeit+=zeit;
      double strecke=land.rundReiseStrecke();
      gesamtstrecke+=strecke;
      System.out.println(land.stadtAnzahl()+" Städte. Zeit="+zeit+"ms. Strecke="+strecke+"km.");
    }
    System.out.println("Gesamtzeit   ="+gesamtzeit   +"ms.");
    System.out.println("Gesamtstrecke="+gesamtstrecke+"km.");
  }

  /**Eine Stadt ist definiert durch ihre Lage im zweidimensionalen Raum.
   * Von zwei Städten wird stets angenommen, dass es eine kürzeste gerade
   * Verbindung in beiden Richtungen gibt, die sich aus, der euklidischen
   * Metrik ergibt (Pythagoras).
   */
  public class Stadt{
    double x,y;
    long id;

    /**Der Konstruktor ist <code>private</code>, damit nur ein Land Städte
     * erzeugen kann.
     * @param x die x-Koordinate der Stadt
     * @param y die y-Koordinate der Stadt
     */
    private Stadt(double x, double y){
      this.x=x;
      this.y=y;
      id=zufall.nextLong();
    }

    public double getX(){return x;}

    public double getY(){return y;}

    /**Gibt die Distanz zu einer anderen Stadt an.
     *
     * @param s die andere Stadt.
     * @return der euklidische Abstand berechnet mit dem Satz von Pythagoras.
     */
    public double distanz(Stadt s){
      return Math.hypot(x-s.x, y-s.y);
    }

    @Override
    public String toString(){
      return "("+x+"|"+y+")";
    }
  }
}
